package cn.wgx.study.algorithm;

import com.sun.prism.impl.shape.BasicRoundRectRep;

import java.util.Arrays;
import java.util.Random;

/**
 * 算法
 * 1. 选择排序 selection
 * 2. 冒泡排序 bubble
 * 3. 插入 insertion
 * 4. 堆排序 heap
 * 5. 希尔排序 shell
 * 6. 归并排序 merge
 * 7. 快速排序 quick
 * 8. 桶排序 bucket
 * 9. 计数排序 counting
 * 10. 基数排序 radix
 */
public class Algorithm  extends SortBase{

    public static void main(String[] args) {
        int[] array = generate(100, 100);
        int[] array2 = Arrays.copyOf(array, array.length);
        print(array);

//        print(select(array));
//        print(bubble(array));
        Arrays.sort(array2);

        print(array2);
        System.out.println(compare(array, array2));
    }



    //1. 选择排序 基础版
    public static int[] select(int[] array) {
        int len = array.length;
        for (int i = 0; i < (len - 1); i++) {
            int min_index = i;
            for (int j = i + 1; j < len; j++)
                if (array[min_index] > array[j])
                    min_index = j;
            if (min_index != i)
                exchange(array, i, min_index);
        }
        return array;
    }

    //1.1 选择排序 高级版
    public static int[] select2(int[] array) {
        int len = array.length;
        for (int i = 0; i < (len - 1); i++) {
            int min_index = i;
            int max_index = i;
            for (int j = i + 1; j < len; j++) {
                if (array[min_index] > array[j]) {
                    min_index = j;
                }
                if (array[max_index] < array[j]) {
                    max_index = j;
                }
            }
            if (min_index != i)
                exchange(array, i, min_index);
            if (max_index != i)
                exchange(array, (len - 1) - i, max_index);
        }
        return array;
    }



}
